`
https://leetcode.cn/problems/maximize-win-from-two-segments/
`

/**
 * @param {number[]} prizePositions
 * @param {number} k
 * @return {number}
 */
var maximizeWin = function (prizePositions, k) {
  // 枚举一条线段，维护另一条线段
  // 思想类似于两数之和，枚举所有的数，在前面找符合的数，但该题枚举的是线段，也就是子数组
  const n = prizePositions.length

  // 如果所有的奖品都可以被直接覆盖，那么所有的奖品都可以被直接拿到
  if (k * 2 + 1 >= prizePositions[n - 1] - prizePositions[0]) return n

  // 维护 pos[i] 之前能获取奖品的最大值
  const pre = new Array(n + 1).fill(0)
  let res = 0
  let left = 0, right = 0

  while (right < n) {
    const p = prizePositions[right++]

    while (p - prizePositions[left] > k) left++

    // 当前线段拿到最多的 + 之前线段拿到最多的
    res = Math.max(res, right - left + pre[left])
    // 更新 pre
    pre[right] = Math.max(pre[right - 1], right - left)
  }

  return res
};